﻿// 215. 破译密码 jinjiezhinan.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://www.acwing.com/problem/content/217/

达达正在破解一段密码，他需要回答很多类似的问题：

对于给定的整数 a,b 和 d
，有多少正整数对 x,y
，满足 x≤a，y≤b
，并且 gcd(x,y)=d。

作为达达的同学，达达希望得到你的帮助。

输入格式
第一行包含一个正整数 n，表示一共有 n 组询问。

接下来 n行，每行表示一个询问，每行三个正整数，分别为 a,b,d。

输出格式
对于每组询问，输出一个正整数，表示满足条件的整数对数。

数据范围
1≤n≤50000
,
1≤d≤a,b≤50000
输入样例：
2
4 5 2
6 4 3
输出样例：
3
2
提示:gcd(x,y) 返回 x，y的最大公约数。
*/


int main()
{
    std::cout << "Hello World!\n";
}

 